package com.lihepeng.leecode.sort;
/**
 * 归并排序
 *
 * @author lihepeng
 */


import org.junit.Test;

import java.util.Arrays;


public class MergeSort {
    public void mergeSort(int[] arrs, int left, int mid, int right) {
        int[] tmp = new int[arrs.length];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (arrs[i] < arrs[j]) {
                tmp[k++] = arrs[i++];
            } else {
                tmp[k++] = arrs[j++];
            }
            while (i <= mid) {
                tmp[k++] = arrs[i++];
            }
            while (j <= right) {
                tmp[k++] = arrs[j++];
            }
            // 将temp 数组中的全部元素拷贝到原数组中
            for (int k2 = 0; k2 < tmp.length; k2++) {
                arrs[k2 + left] = tmp[k2];
            }

        }


    }

    /**
     * merge sort review
     * merge Sort 是合并排序的重要变现形式
     *
     * 2021年7月13日
     */
    public void mergeSort(int []arrss){
        int n = arrss.length;
        mergeSort01(arrss,0,n-1);

    }

    private void mergeSort01(int[] arrss, int left, int right) {
        if (left >=right) {
            return ;
        }
        int mid = left+ (right-left)/2;
        mergeSort01(arrss,left,mid);
        mergeSort01(arrss,mid,right);
        merge(arrss,left,mid,right);

    }

    private void merge(int[] arrs, int left, int mid, int right) {
        int[] aux = Arrays.copyOfRange(arrs, left, right + 1);
        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
        int i = left, j = mid + 1;
        for (int k = left; k <= right; k++) {
            if (i > mid) {  // 如果左半部分元素已经全部处理完毕
                arrs[k] = aux[j - left];
                j++;
            } else if (j > right) {   // 如果右半部分元素已经全部处理完毕
                arrs[k] = aux[i - left];
                i++;
            } else if (aux[i - left]<(aux[j - left]) ) {  // 左半部分所指元素 < 右半部分所指元素
                arrs[k] = aux[i - left];
                i++;
            } else {  // 左半部分所指元素 >= 右半部分所指元素
                arrs[k] = aux[j - left];
                j++;
            }
        }
    }

    @Test
    public void runTest01() {
        int[]arrs = {1,7,3,2,5,6,9};
        mergeSort(arrs);
        System.out.println(Arrays.toString(arrs));
    }
}
